package com.xie.leetcode.algorithm;

//240. 搜索二维矩阵 II
//        编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
//
//        每行的元素从左到右升序排列。
//        每列的元素从上到下升序排列。
//
//
//        示例 1：
//
//
//        输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
//        输出：true
//        示例 2：
//
//
//        输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
//        输出：false
//
//
//        提示：
//
//        m == matrix.length
//        n == matrix[i].length
//        1 <= n, m <= 300
//        -109 <= matrix[i][j] <= 109
//        每行的所有元素从左到右升序排列
//        每列的所有元素从上到下升序排列
//        -109 <= target <= 109

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiezhendong
 * @date 2021/10/25
 */
public class SearchMatrix {

    public static void main(String[] args) {
        SearchMatrix searchMatrix = new SearchMatrix();
        int[][] matrix = new int[][]{
                new int[]{1, 4, 7, 11, 15},
                new int[]{2, 5, 8, 12, 19},
                new int[]{3, 6, 9, 16, 22},
                new int[]{10, 13, 14, 17, 24},
                new int[]{18, 21, 23, 26, 30}};
        System.out.println(searchMatrix.searchMatrix(matrix, 5));
        matrix = new int[][]{
                new int[]{1, 4, 7, 11, 15},
                new int[]{2, 5, 8, 12, 19},
                new int[]{3, 6, 9, 16, 22},
                new int[]{10, 13, 14, 17, 24},
                new int[]{18, 21, 23, 26, 30}};
        System.out.println(searchMatrix.searchMatrix(matrix, 20));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int row = 0;
        int cel = n - 1;
        while (row <= m - 1 && cel >= 0) {
            if (matrix[row][cel] == target) {
                return true;
            }
            if (matrix[row][cel] < target) {
                row++;
            } else if (matrix[row][cel] > target) {
                cel--;
            }
        }

        return false;
    }

    /**
     * 二分法查询
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        List<Integer> mL = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] <= target && target <= matrix[i][n - 1]) {
                mL.add(i);
            }
        }
        for (Integer integer : mL) {
            for (int j = 0; j < n; j++) {
                if (matrix[integer][j] == target) {
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * 暴力遍历
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }

        return false;
    }
}
